import java.util.*;

/** 
 * Specializza la classe AlgorithmBase implementando la logica di calcolo dei
 * percorsi minimi secondo l'algoritmo di Dijkstra. 
 * L'algoritmo di Dijkstra non è in grado di calcolare correttamente
 * le distanze in presenza di cicli negativi, né è in grado di rilevarli 
 * correttamente. Per individuare la presenza di cicli negativi avvalersi
 * dell'algoritmo di BellmanFord  
 * @see BellmanFord   
 * 
 * @author Massimiliano Ferretti matricola 79769 
 */

 public class Dijkstra 
  extends AlgorithmBase
  {
    private List<Node> set;
  
    public String getName()
    {
      return "Dijkstra";
    }
    
    private void makeset()
    {
      set = new ArrayList<Node>();
    
      for(Node node : nodes)
        set.add(node);
    }
    
    private Node deletemin()
    {
      if(set.size() == 0)
          return null;
    
      Node current = null;
      
      for(Node node : set)
      {
        if(current == null || node.getDistance() < current.getDistance())
          current = node;
      }
      
      if(current != null)
        set.remove(current);
    
      return current;
    }                         
    
    public void execute()
    {
      makeset();
      
      // System.out.println("Inizio " + getName() + "\n");
      log("Inizio " + getName());
      
      while(true)
      {
        Node node = deletemin();
    
        if(node == null)
            break; // Ho finito i nodi da controllare

        if(node.isDistanceInfinite())
        {
          // System.out.println("Estratto nodo " + node.getIndex() + " a distanza infinita. Non puo apportare miglioramenti, quindi viene saltato ");
          log("Estratto nodo " + node.getIndex() + " a distanza infinita. Non puo apportare miglioramenti, quindi viene saltato ");
          continue;          
        }

        // System.out.println("Estratto nodo " + node.getIndex() + " a distanza: " + node.getDistance());
        log("Estratto nodo " + node.getIndex() + " a distanza: " + node.getDistance());
        
        for(Arc arc : arcs)
        {
          if(arc.getSource().getIndex() == node.getIndex())
          {
            if(!arc.isComplete())
            {
              // System.out.println("Trovato arco incompleto, saltato");
              log("Trovato arco incompleto, saltato");
              continue;
            }
          
            // Relax
            if(node.getDistance() + arc.getWeight() < arc.getTarget().getDistance())
            {
              Node target = arc.getTarget();
              int newDistance = node.getDistance() + arc.getWeight();                            

              String oldDistance = Integer.toString(target.getDistance());
              if(target.isDistanceInfinite())
                oldDistance = "infinito";
                                                                                  
              // System.out.println("(" + arc.getSource().getIndex() + "->" + target.getIndex() + ") Nodo: " + target.getIndex() + " relax da: " + target.getDistance() + " a: " + newDistance);
              log("(" + arc.getSource().getIndex() + "->" + target.getIndex() + ") Nodo: " + target.getIndex() + " relax da: " + oldDistance + " a: " + newDistance);
              
              arc.getTarget().setDistance(newDistance);
              arc.getTarget().setPrevious(node);
            } else
            {
              // Non c'e bisogno di Relax
              Node target = arc.getTarget();
              // System.out.println("Nodo: " + target.getIndex() + " rimane a: " + target.getDistance() + ", non ha bisogno di relax");
              log("Nodo: " + target.getIndex() + " rimane a: " + target.getDistance() + ", non ha bisogno di relax");
            }
          }
        }      
      }
    }
}
